class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int ret = 0;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                int num = nums[i] + nums[j];
                int p = lower_bound(nums.begin()+j+1,nums.end(),num)-nums.begin()-j-1;
                ret += p;
            }
        }
        return ret;
    }
};
